package leetcode2;

public class Day10 {


    //递归 -- 直到只有一个节点
    /*public ListNode sortInList (ListNode head) {
        // write code here
        if(head == null || head.next == null) return head;
        //保证有两个结点
        ListNode slow = head;
        ListNode mid = head.next;
        ListNode fast = head.next.next;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            mid = mid.next;
        }
        slow.next=null;//将单链表分成两半
        return merge(sortInList(head),sortInList(mid));
    }

    //合并两个有序链表
    private ListNode merge(ListNode left,ListNode right) {
        //1.处理一个为空另一个不为空的情况
        //2.处理两个链表都有值的情况(合并两个有序链表)

        if(left == null) return right;
        if(right == null) return left;

        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        ListNode cur1 = left;
        ListNode cur2 = right;
        while(cur1 != null && cur2 != null) {
            if(cur1.val > cur2.val) {
                cur.next = cur2;
                cur = cur.next;
                cur2 = cur2.next;
            }else {
                cur.next = cur1;
                cur = cur.next;
                cur1 = cur1.next;
            }
        }
        if(cur1 != null) {
            cur.next = cur1;
        }else {
            cur.next = cur2;
        }
        return newHead.next;
    }*/
}
